package study1;

import java.util.Arrays;
import java.util.List;

public class InorderTraversalTest {

    public static void main(String[] args) {
        // 构建测试用的二叉树
        /*
         *      1
         *     / \
         *    2   3
         *   /   / \
         *  4    5   6
         */
        InorderTraversal.TreeNode root = new  InorderTraversal.TreeNode(1);
        root.left = new  InorderTraversal.TreeNode(2);
        root.right = new  InorderTraversal.TreeNode(3);
        root.left.left = new  InorderTraversal.TreeNode(4);
        root.right.left = new  InorderTraversal.TreeNode(5);
        root.right.right = new  InorderTraversal.TreeNode(6);

        InorderTraversal traversal = new InorderTraversal();

        // 测试1：正常二叉树
        System.out.println("Test Case 1: Normal Binary Tree");
        testTraversal(traversal, root, Arrays.asList(4, 2, 1, 5, 3, 6));

        // 测试2：空树
        System.out.println("\nTest Case 2: Empty Tree");
        testTraversal(traversal, null, Arrays.asList());

        // 测试3：只有根节点
        System.out.println("\nTest Case 3: Single Node");
        InorderTraversal.TreeNode singleNode = new  InorderTraversal.TreeNode(100);
        testTraversal(traversal, singleNode, Arrays.asList(100));

        // 测试4：只有左子树
        System.out.println("\nTest Case 4: Left-Skewed Tree");
        InorderTraversal.TreeNode leftSkewed = new  InorderTraversal.TreeNode(10);
        leftSkewed.left = new  InorderTraversal.TreeNode(20);
        leftSkewed.left.left = new  InorderTraversal.TreeNode(30);
        testTraversal(traversal, leftSkewed, Arrays.asList(30, 20, 10));

        // 测试5：只有右子树
        System.out.println("\nTest Case 5: Right-Skewed Tree");
        InorderTraversal.TreeNode rightSkewed = new  InorderTraversal.TreeNode(10);
        rightSkewed.right = new  InorderTraversal.TreeNode(20);
        rightSkewed.right.right = new  InorderTraversal.TreeNode(30);
        testTraversal(traversal, rightSkewed, Arrays.asList(10, 20, 30));

        // 测试6：复杂二叉树
        System.out.println("\nTest Case 6: Complex Tree");
        InorderTraversal.TreeNode complex = new  InorderTraversal.TreeNode(25);
        complex.left = new  InorderTraversal.TreeNode(15);
        complex.right = new  InorderTraversal.TreeNode(50);
        complex.left.left = new  InorderTraversal.TreeNode(10);
        complex.left.right = new  InorderTraversal.TreeNode(22);
        complex.right.left = new  InorderTraversal.TreeNode(35);
        complex.right.right = new  InorderTraversal.TreeNode(70);
        complex.left.left.left = new  InorderTraversal.TreeNode(4);
        complex.left.left.right = new  InorderTraversal.TreeNode(12);
        complex.right.left.right = new  InorderTraversal.TreeNode(44);
        testTraversal(traversal, complex, Arrays.asList(4, 10, 12, 15, 22, 25, 35, 44, 50, 70));
    }

    private static void testTraversal(InorderTraversal traversal,  InorderTraversal.TreeNode root, List<Integer> expected) {
        // 测试递归方法
        testMethod(traversal.inorderTraversal(root), expected, "Recursive Method");

        // 测试迭代方法
        testMethod(traversal.inorderTraversal2(root), expected, "Iterative Method");

        // 测试Morris遍历
        testMethod(traversal.inorderTraversal4(root), expected, "Morris Traversal");

        // 测试颜色标记法
        testMethod(traversal.inorderTraversal4(root), expected, "Color Marking Method");
    }

    private static void testMethod(List<Integer> result, List<Integer> expected, String methodName) {
        System.out.println(methodName + ":");
        System.out.println("  Expected -> " + expected);
        System.out.println("  Actual   -> " + result);

        if (result.equals(expected)) {
            System.out.println("  ✅ Passed");
        } else {
            System.out.println("  ❌ Failed");
        }
    }
}
